public class Test1 {
    //leetcode 1049 最后一块石头的重量II
    public int lastStoneWeightII(int[] stones) {
        //这个题目可以转换为将数组分为两个部分，使得两个部分的绝对值的和尽量接近，也就是一部分的和尽量接近
        //整个数组和的二分之一，所以这个问题就可以看作是背包问题，从数组的前i个元素中选取数字
        //使得选取的数字之和接近于j
        //状态表示：dp[i][j]表示从前i个物品中选择物品装入背包中，使得背包中的物品的体积和不大于j时物品的最大体积
        int sum = 0;
        for (int n : stones) sum += n;
        int n = stones.length, aim = sum / 2;
        //状态转移方程：当前第i个物品的情况分为装和不装，如果不装，那么dp[i][j] = dp[i-1][j]
        //如果装，dp[i][j] = dp[i-1][j - stones[i]] + stones[i]
        int[][] dp = new int[n + 1][aim + 1];
        //初始化，因为要用到i-1，所以需要对i为0的时候做出初始化,第0行意思是从前0个物品中选择物品，使得背包容量
        //为0，1，2...时不超过背包容量的最大体积，那么值就为0
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= aim; j++) {
                //第i个物品不装的时候
                dp[i][j] = dp[i-1][j];
                //第i个物品选择装入的情况，需要保证当前背包的容量要大于第i个物品的体积
                if (j >= stones[i - 1]) dp[i][j] = Math.max(dp[i][j],dp[i-1][j - stones[i-1]] + stones[i-1]);
            }
        }
        return sum - 2 * dp[n][aim];
    }

    //优化
    public int lastStoneWeightII1(int[] stones) {
        //这个题目可以转换为将数组分为两个部分，使得两个部分的绝对值的和尽量接近，也就是一部分的和尽量接近
        //整个数组和的二分之一，所以这个问题就可以看作是背包问题，从数组的前i个元素中选取数字
        //使得选取的数字之和接近于j
        //状态表示：dp[i][j]表示从前i个物品中选择物品装入背包中，使得背包中的物品的体积和不大于j时物品的最大体积
        int sum = 0;
        for (int n : stones) sum += n;
        int n = stones.length, aim = sum / 2;
        //状态转移方程：当前第i个物品的情况分为装和不装，如果不装，那么dp[i][j] = dp[i-1][j]
        //如果装，dp[i][j] = dp[i-1][j - stones[i]] + stones[i]
        int[] dp = new int[aim + 1];
        //初始化，因为要用到i-1，所以需要对i为0的时候做出初始化,第0行意思是从前0个物品中选择物品，使得背包容量
        //为0，1，2...时不超过背包容量的最大体积，那么值就为0
        for (int i = 1; i <= n; i++) {
            for (int j = aim; j >= stones[i-1]; j--) {
                //第i个物品选择装入的情况，需要保证当前背包的容量要大于第i个物品的体积
                dp[j] = Math.max(dp[j],dp[j - stones[i-1]] + stones[i-1]);
            }
        }
        return sum - 2 * dp[aim];
    }
}
